Within the context of Valiant's protocol for learning, the Perceptron algorithm is shown to learn an arbitrary half-space in time O(r;;) if D, the proba(cid:173) bility distribution of examples, is taken uniform over the unit sphere sn. Here f is the accuracy parameter. This is surprisingly fast, as "standard" approaches involve solution of a linear programming problem involving O( 7') constraints in n dimen(cid:173) sions. A modification of Valiant's distribution independent protocol for learning is proposed in which the distribution and the function to be learned may be cho(cid:173) sen by adversaries, however these adversaries may not communicate. It is argued that this definition is more reasonable and applicable to real world learning than Valiant's.